package leetcode.pre100;

import leetcode.top100.Code64_MinPathSum_最小路径和;

import java.util.Arrays;

/**
 *一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 *
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 *
 * 问总共有多少条不同的路径？
 *
 *
 *输入: m = 3, n = 2
 * 输出: 3
 * 解释:
 * 从左上角开始，总共有 3 条路径可以到达右下角。
 * 1. 向右 -> 向右 -> 向下
 * 2. 向右 -> 向下 -> 向右
 * 3. 向下 -> 向右 -> 向右
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/unique-paths
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
。
 * 本质同
 * {@link Code63_DifferentPaths_不同路径2}
 *
 * 动态规划见
 * {@link leetcode.a_总结分布.Code01_DP}
 * @since 2019/12/1 0001 下午 3:35
 */
public class Code62_DifferentPaths_不同路径 {
    public static void main(String[] args) {
        System.out.println(uniquePaths(7, 3));
    }
    public static int uniquePaths(int m, int n) {
        if(m <=0 || n <=0 ){
            return 0;
        }
        if(m == 1 || n == 1){
            return 1;
        }
        //方式1：回溯
//        return process(0,0,m-1,n-1);
        //方式2：DP
//        return dpProcess(m,n);
        return dpProcess1(m,n);
    }

    /**
     * DP:时间O(m*n)，空间O(m*n)，空间可以优化到O(2n)甚至是O(n)
     */
    private static int dpProcess(int m, int n) {
        int row = m - 1;
        int col = n - 1;
        int [][] dp = new int[row+1][col+1];
        dp[row][col] = 0;

        //最后一行都是1种
        for (int i = 0; i < col; i++) {
            dp[row][i] = 1;
        }
        //最后一列都是1种
        for (int i = 0; i < row ; i++) {
            dp[i][col] = 1;
        }
        //填充表。按行或列填充都行
        //这里按行填充
        for (int i = row - 1; i >= 0 ; i--) {
            for (int j = col - 1; j >= 0 ; j--) {
                //当前方法数 = 下 + 右 方法数
                dp[i][j] = dp[i+1][j] + dp[i][j+1];
            }
        }
        return dp[0][0];
    }

    /**
     * 优化空间到O(2n)
     */
    private static int dpProcess1(int m, int n) {
        //当前行的种数。i代表第i列。
        int [] cur = new int[n];
        //下一行的种数，位置i代表第i列上的种数
        int [] pre = new int[n];
        //最后一行最后一列都填充为1
        Arrays.fill(cur,1);
        Arrays.fill(pre,1);
        for (int i = m-2; i >= 0; i--) {
            for (int j = n - 2; j >= 0 ; j--) {
                //当前行的第j列 = 下一行的第j列 + 当前行的第 j+1列
                cur[j] = pre[j] + cur[j+1];
            }
            //当前行的元素 赋值给 上一行。
            pre = cur.clone();
        }
        return cur[0];
    }
    /**
     * 方式2：记忆性回溯
     */

    private static int process2(int m, int n) {
        if(m <= 0 || n <= 0) return 0;
        if(m == 1 || n == 1) return 1;
        int [][]memo = new int[m][n];
        doProcess2(0,0,m-1,n-1,memo);
        return memo[0][0];
    }

    private static int doProcess2(int i, int j, int m, int n, int[][] memo) {
        //来到了最后行或最后一列，直接返回。只有1种走法
        if(i == m  || j == n ){
            return 1;
        }
        if(memo[i][j] != 0) return memo[i][j];
        //否则当前走法等于下走法 + 右走法
        memo[i][j] = doProcess2(i+1,j,m,n,memo) + doProcess2(i,j+1,m,n,memo);
        return memo[i][j];
    }
    /**
     * 回溯超时
     */
    private static int process(int i, int j, int m, int n) {
        //来到了最后行或最后一列，直接返回。只有1种走法
        if(i == m || j == n){
            return 1;
        }
        //否则当前走法等于下走法 + 右走法
        return process(i+1,j,m,n) + process(i,j+1,m,n);
    }
}
